//
//  SortedArrayToBST.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/7/3.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  108. 将有序数组转换为二叉搜索树  tag:树 深度优先搜索

import UIKit

/*
 108. 将有序数组转换为二叉搜索树
 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

 示例:

 给定有序数组: [-10,-3,0,5,9],

 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

       0
      / \
    -3   9
    /   /
  -10  5
 */

class SortedArrayToBST: NSObject {
    
    func sortedArrayToBST(_ nums: [Int]) -> TreeNode? {

        return self.helper(nums, 0, nums.count - 1)
    }
    
    func helper(_ nums: [Int], _ left:Int, _ right:Int) -> TreeNode?{
        if left > right{
            return nil
        }
        
        let mid = (left+right)/2
        let node = TreeNode(nums[mid])
        node.left = helper(nums, left, mid - 1)
        node.right = helper(nums, mid + 1, right)
        return node
    }
}
